#include<bits/stdc++.h>
using namespace std;
const int N=210,M=N*N;
int T,n,m,res,mod,inv2,dp[N][M];
inline void upd(int &x,int y) {x+=y;if(x>=mod) x-=mod;}
int ksm(int x,int y)
{
	int res=1;
	for(;y;y>>=1)
	{
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;
	}
	return res;
}
int main()
{
	freopen("pr.in","r",stdin);
	freopen("pr.out","w",stdout);
	scanf("%d%d",&mod,&T);
	inv2=(mod+1)/2;
	dp[0][0]=1;
	while(T--)
	{
		scanf("%d%d",&n,&m);res=0;
		for(int i=1;i<=n;i++)
			for(int j=0;j<=n*m;j++) dp[i][j]=0;
		for(int i=1;i<=n;i++)
			for(int j=0;j<=m;j++)
				for(int k=0;k<=i*m;k++) upd(dp[i][j+k],dp[i-1][k]);
		for(int i=0;i<=n*m;i++) upd(res,1ll*dp[n][i]*dp[n][i]%mod);
		res=1ll*res*ksm(ksm(m+1,n+n),mod-2)%mod;
		printf("%d\n",1ll*(1-res+mod)*inv2%mod);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}
